package datastructure.hash;

import java.util.HashMap;
import java.util.TreeMap;

/**
 * @Description: 自定义哈希表, 自己实现哈希函数
 * @author: Yang Qiang
 * @create: 2021-11-27 16:40
 */
public class HashTable<K,V>{
    // 使用TreeMap 作为底层哈希表, 底层是一个数组, 数组的属性是HashTable
    // 这里TreeMap<K,V>[16]  其实就等于  HashMap(16)
    private TreeMap<K,V>[] hashTable;
    // 哈希表定义的长度
    private int length;
    // 哈希表的数据个数
    private int size;


    /**
     * 无参构造
     */
    public HashTable(){
        this(10);
    }
    /**
     * 有参构造
     * @param length
     */
    public HashTable(int length){
        this.length = length;
        size = 0;
        // 初始化哈希表长度
        hashTable = new TreeMap[length];
        for (int i = 0; i < length; i++) {
            // 为哈希表初始化
            hashTable[i] = new TreeMap();
        }
    }

    /**
     * 获取哈希表的元素个数
     * @return
     */
    public int getSize() {
        return size;
    }

    /**
     * 哈希表增加元素
     * 如果key存在就修改, 如果key不存在就新增
     * @param key
     * @param value
     */
    public void add(K key, V value){
        // 根据key计算索引值
        int index = hashKey(key);
        // 根据索引的到指定位置的值
        TreeMap<K, V> treeMap = hashTable[index];
        // 有就修改-没有就增加
        if (treeMap.containsKey(key)){
            treeMap.put(key, value);
        }else {
            treeMap.put(key, value);
            size++;
        }
    }

    /**
     * 删除元素, 并返回值
     * @param key
     * @return
     */
    public V remove(K key){
        int index = hashKey(key);
        TreeMap<K, V> treeMap = hashTable[index];
        if (treeMap.containsKey(key)){
            size--;
            return treeMap.remove(key);
        }
        return null;
    }

    /**
     * 获取哈希表中的值
     * @param key
     * @return
     */
    public V get(K key){
        return hashTable[hashKey(key)].get(key);
    }


    /**
     * 自定义哈希函数
     * 利用object类的HashCode方法, 然后最后对总容量进行取余
     * @param key
     * @return
     */
    public int hashKey(K key){
        return (key.hashCode() & 0x7fffffff) % length;
    }

}
